//学校的自助午餐提供圆形和方形的三明治，分别用数字 0 和 1 表示。所有学生站在一个队列里，每个学生要么喜欢圆形的要么喜欢方形的。 
//餐厅里三明治的数量与学生的数量相同。所有三明治都放在一个 栈 里，每一轮： 
//
// 
// 如果队列最前面的学生 喜欢 栈顶的三明治，那么会 拿走它 并离开队列。 
// 否则，这名学生会 放弃这个三明治 并回到队列的尾部。 
// 
//
// 这个过程会一直持续到队列里所有学生都不喜欢栈顶的三明治为止。 
//
// 给你两个整数数组 students 和 sandwiches ，其中 sandwiches[i] 是栈里面第 i 个三明治的类型（i = 0 是栈的顶部）
//， students[j] 是初始队列里第 j 名学生对三明治的喜好（j = 0 是队列的最开始位置）。请你返回无法吃午餐的学生数量。 
//
// 
//
// 示例 1： 
//
// 输入：students = [1,1,0,0], sandwiches = [0,1,0,1]
//输出：0 
//解释：
//- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,0,0,1]。
//- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,0,1,1]。
//- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [0,1,1]，三明治栈为 sandwiches = [1,0,1]。
//- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [1,1,0]。
//- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1,0]，三明治栈为 sandwiches = [0,1]。
//- 最前面的学生放弃最顶上的三明治，并回到队列的末尾，学生队列变为 students = [0,1]。
//- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = [1]，三明治栈为 sandwiches = [1]。
//- 最前面的学生拿走最顶上的三明治，剩余学生队列为 students = []，三明治栈为 sandwiches = []。
//所以所有学生都有三明治吃。
// 
//
// 示例 2： 
//
// 输入：students = [1,1,1,0,0,1], sandwiches = [1,0,0,0,1,1]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// 1 <= students.length, sandwiches.length <= 100 
// students.length == sandwiches.length 
// sandwiches[i] 要么是 0 ，要么是 1 。 
// students[i] 要么是 0 ，要么是 1 。 
// 
// Related Topics栈 | 队列 | 数组 | 模拟 
//
// 👍 75, 👎 0 
//
//
//
//

package leetcode.editor.day;

// 1700. 无法吃午餐的学生数量
// https://leetcode.cn/problems/number-of-students-unable-to-eat-lunch/
class NumberOfStudentsUnableToEatLunch {
    public static void main(String[] args) {
        Solution solution = new NumberOfStudentsUnableToEatLunch().new Solution();
        solution.countStudents(new int[]{1, 1, 0, 0}, new int[]{0, 1, 0, 1});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 使用队列
        /*public int countStudents(int[] students, int[] sandwiches) {
            Queue<Integer> queue = new LinkedList<>();
            for (int student : students) {
                queue.offer(student);
            }

            int idx = 0, m = sandwiches.length;
            while (idx < m) {
                int size = queue.size();
                boolean flag = false;
                for (int i = 0; i < size; i++) {
                    Integer poll = queue.poll();
                    if (poll == sandwiches[idx]) {
                        idx++;
                        flag = true;
                    } else queue.offer(poll);
                }

                if (!flag) break;
            }

            return queue.size();
        }*/

        // 简单模拟
        // 根据题意进行模拟即可 : 当学生遇到喜欢的种类会进行匹配，否则会轮到队列尾部，而面包则是一直停在栈顶位置等待匹配。
        // 因此当且仅当栈顶的面包种类没有待匹配的学生种类与之相对应时，整个匹配过程结束。
        public int countStudents(int[] students, int[] sandwiches) {
            int[] cnt = new int[2];
            for (int s : students) cnt[s]++;
            for (int i = 0; i < sandwiches.length; i++) {
                if (--cnt[sandwiches[i]] == -1) return sandwiches.length - i;
            }
            return 0;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
